#include "Sort.h"

void Sort_Bucket(int *Array, int Offset, int Length)
{
	int Index, Found, SmallValue, SmallBucket, Bucket, Buckets=(Length-1)/4+1, Indexes[Buckets], Array2[Length];
	
	//Copy over data
	for(Index=0;Index<Length;++Index)
		Array2[Index]=Array[Index+Offset];
	
	//Sort each bucket
	Index=0;
	while(Index<Length)
	{
		switch(Length-Index)
		{
			case 1:
			break;
			case 2:
				Sort_Rapid2(Array2, Index);
			break;
			case 3:
				Sort_Rapid3(Array2, Index);
			break;
			default:
				Sort_Rapid4(Array2, Index);
			break;
		}
		Index+=4;
	}
	
	//Merge back together
	for(Bucket=0;Bucket<Buckets;++Bucket)
		Indexes[Bucket]=0;
		
	SmallValue=SmallBucket=0;
	for(Index=0;Index<Length;++Index)
	{
		Found=0;
		for(Bucket=0;Bucket<Buckets;++Bucket)
		{
			if (Indexes[Bucket]<4 && (Indexes[Bucket]+Bucket*4)<Length && (Found==0 || Array2[Indexes[Bucket]+Bucket*4]<SmallValue))
			{
				Found=1;
				SmallValue=Array2[Indexes[Bucket]+Bucket*4];
				SmallBucket=Bucket;
			}
		}
		
		Array[Index+Offset]=SmallValue;
		++Indexes[SmallBucket];
	}
}

void Sort_Dan(int *Array, int Offset, int Length)
{
	int Temp, Index, SmallValue, SmallIndex, BigValue, BigIndex;
	
	switch(Length)
	{
		case -1:
		case 0:
		case 1:
			return;
		break;
		case 2:
			if (Array[Offset]>Array[Offset+1])
			{
				Temp=Array[Offset];
				Array[Offset]=Array[Offset+1];
				Array[Offset+1]=Temp;
			}
			return;
		break;
		case 3:
			Sort_Rapid3(Array, Offset);
			return;
		break;
		case 4:
			Sort_Rapid4(Array, Offset);
			return;
		break;
		default:
			SmallValue=Array[Offset];
			BigValue=Array[Offset];
			SmallIndex=Offset;
			BigIndex=Offset;
			for(Index=Offset;Index<Offset+Length;++Index)
			{
				Temp=Array[Index];
				
				if (Temp<SmallValue)
				{
					SmallValue=Temp;
					SmallIndex=Index;
				}
				else if(Temp>BigValue)
				{
					BigValue=Temp;
					BigIndex=Index;
				}
			}
			
			Temp=Array[Offset];
			Array[Offset]=Array[SmallIndex];
			Array[SmallIndex]=Temp;
			
			Temp=Array[Offset+Length-1];
			Array[Offset+Length-1]=Array[BigIndex];
			Array[BigIndex]=Temp;
			
			Sort_Dan(Array, Offset+1, Length-2);
		break;
	}
}

void Sort_Quick(int *Array, int Offset, int Length)
{
	int Temp, Pivot, Index, SwapIndex;
	
	switch(Length)
	{
		case -1:
		case 0:
		case 1:
			return;
		break;
		case 2:
			if (Array[Offset]>Array[Offset+1])
			{
				Temp=Array[Offset];
				Array[Offset]=Array[Offset+1];
				Array[Offset+1]=Temp;
			}
			return;
		break;
		case 3:
			Sort_Rapid3(Array, Offset);
			return;
		break;
		case 4:
			Sort_Rapid4(Array, Offset);
			return;
		break;
		/*case 5:
			Sort_Rapid5(Array, Offset);
			return;
		break;*/
		default:
			//Use last value as pivot
			Pivot=Array[Offset+Length-1];
			
			for(Index=SwapIndex=Offset;Index<Offset+Length;++Index)
			{
				if ((Temp=Array[Index])<=Pivot)
				{
					Array[Index]=Array[SwapIndex];
					Array[SwapIndex++]=Temp;
				}
			}
			
			/* Now sort each part */
			Sort_Quick(Array, Offset, SwapIndex-Offset-1);
			Sort_Quick(Array, SwapIndex, (Offset+Length)-SwapIndex);
			return;
		break;
	}
}

void Sort_Bubble(int *Array, int Offset, int Length)
{
	int Changes=1, Index, Temp;
	
	while(Changes)
	{
		Changes=0;
		
		for(Index=Offset;Index+1<Offset+Length;++Index)
		{
			Temp=Array[Index];
			
			if(Temp>Array[Index+1])
			{
				Changes=1;
				
				Array[Index]=Array[Index+1];
				Array[Index+1]=Temp;
			}
		}
	}
	
	return;
}

void Sort_Heap(int *Array, int Offset, int Length)
{
	int CurrentLength, Index, BiggestIndex, BiggestValue;
	
	for(CurrentLength=Length;CurrentLength>1;--CurrentLength)
	{
		Index=Offset;
		
		BiggestValue=Array[Index];
		BiggestIndex=Index;
		++Index;
		while(Index<CurrentLength+Offset)
		{
			if (Array[Index]>BiggestValue)
			{
				BiggestValue=Array[Index];
				BiggestIndex=Index;
			}
			
			++Index;
		}
		
		Array[BiggestIndex]=Array[CurrentLength+Offset-1];
		Array[CurrentLength+Offset-1]=BiggestValue;
	}
	
	return;
}


void Sort_Cocktail(int *Array, int Offset, int Length)
{
	int Changes=1, Index, Temp;
	
	while(Changes)
	{
		Changes=0;
		
		for(Index=Offset;Index+1<Offset+Length;++Index)
		{
			Temp=Array[Index];
			
			if(Temp>Array[Index+1])
			{
				Changes=1;
				
				Array[Index]=Array[Index+1];
				Array[Index+1]=Temp;
			}
		}
		for(Index=Offset+Length-1;Index>0;--Index)
		{
			Temp=Array[Index];
			
			if(Temp<Array[Index-1])
			{
				Changes=1;
				
				Array[Index]=Array[Index-1];
				Array[Index-1]=Temp;
			}
		}
	}
	
	return;
}

void Sort_Insert(int *Array, int Offset, int Length)
{
	int InputArray[Length];
	int Index, InputIndex, Current, OutputIndex, ShiftIndex;
	
	/* Copy over Array */
	for(Index=0;Index<Length;++Index)
		InputArray[Index]=Array[Index+Offset];
	
	for(InputIndex=0;InputIndex<Length;++InputIndex)
	{
		Current=InputArray[InputIndex];
		
		if (InputIndex!=0)
		{		
			Index=0;
			OutputIndex=InputIndex;
			while(Index<InputIndex)
			{
				if (Current<Array[Index+Offset])
				{
					OutputIndex=Index;
					Index=InputIndex;
				}
				
				++Index;
			}
			OutputIndex+=Offset;
			
			/* Shift everything forward */
			for(ShiftIndex=InputIndex+1+Offset;ShiftIndex>OutputIndex;--ShiftIndex)
				Array[ShiftIndex]=Array[ShiftIndex-1];
		}
		else
			OutputIndex=0;
		
		/* Put value in right place */
		Array[OutputIndex]=Current;
	}
	
	
	return;
}

inline void Sort_Rapid2(int *Array, int Offset)
{
	int Temp;
	if (Array[Offset]>Array[Offset+1])
	{
		Temp=Array[Offset];
		Array[Offset]=Array[Offset+1];
		Array[Offset+1]=Temp;
	}
	
	return;
}

inline void Sort_Rapid3(int *Array, int Offset)
{
	int A=Array[Offset+0];
	int B=Array[Offset+1];
	int C=Array[Offset+2];
	
	if (A>B)
	{
		//A>B
		if (B>C)
		{
			//A>B>C
			Array[Offset+0]=C;Array[Offset+1]=B;Array[Offset+2]=A;return;
		}
		else
		{
			//A>B C>B
			if (A>C)
			{
				//A>C>B
				Array[Offset+0]=B;Array[Offset+1]=C;Array[Offset+2]=A;return;
			}
			else
			{
				//C>A>B
				Array[Offset+0]=B;Array[Offset+1]=A;Array[Offset+2]=C;return;
			}
		}
	}
	else
	{
		//B>A
		if (A>C)
		{
			//B>A>C
			Array[Offset+0]=C;Array[Offset+1]=A;Array[Offset+2]=B;return;
		}
		else
		{
			//B>A C>A
			if (B>C)
			{
				//B>C>A
				Array[Offset+0]=A;Array[Offset+1]=C;Array[Offset+2]=B;return;
			}
			else
			{
				//C>B>A
				Array[Offset+0]=A;Array[Offset+1]=B;Array[Offset+2]=C;return;
			}
		}
	}
}

inline void Sort_Rapid4(int *Array, int Offset)
{
	int A=Array[Offset+0];
	int B=Array[Offset+1];
	int C=Array[Offset+2];
	int D=Array[Offset+3];
	
	if (A>B)
	{
		// A>B
		if (C>D)
		{
			// A>B C>D
			if (C>A)
			{
				// C>A>B C>D
				if (D<A)
				{
					// C>A>B C>D D<A
					if (D<B)
					{
						// C>A>B>D
						Array[Offset+0]=D;Array[Offset+1]=B;Array[Offset+2]=A;Array[Offset+3]=C;return;
					}
					else
					{
						// C>A>D>B
						Array[Offset+0]=B;Array[Offset+1]=D;Array[Offset+2]=A;Array[Offset+3]=C;return;
					}
				}
				else
				{
					// C>D>A>B
					Array[Offset+0]=B;Array[Offset+1]=A;Array[Offset+2]=D;Array[Offset+3]=C;return;
				}
			}
			else
			{
				// A>B A>C C>D
				if (B>C)
				{
					//A>B>C>D
					Array[Offset+0]=D;Array[Offset+1]=C;Array[Offset+2]=B;Array[Offset+3]=A;return;
				}
				else
				{
					//A>C>B C>D
					if (D>B)
					{
						//A>C>D>B
						Array[Offset+0]=B;Array[Offset+1]=D;Array[Offset+2]=C;Array[Offset+3]=A;return;
					}
					else
					{
						//A>C>B>D
						Array[Offset+0]=D;Array[Offset+1]=B;Array[Offset+2]=C;Array[Offset+3]=A;return;
					}
				}
			}
		}
		else
		{
			// A>B D>C
			if (D>A)
			{
				//D>A>B D>C
				if (C>B)
				{
					//D>A>B D>C>B
					if (C>A)
					{
						//D>C>A>B
						Array[Offset+0]=B;Array[Offset+1]=A;Array[Offset+2]=C;Array[Offset+3]=D;return;
					}
					else
					{
						//D>A>C>B
						Array[Offset+0]=B;Array[Offset+1]=C;Array[Offset+2]=A;Array[Offset+3]=D;return;
					}
				}
				else
				{
					//D>A>B>C
					Array[Offset+0]=C;Array[Offset+1]=B;Array[Offset+2]=A;Array[Offset+3]=D;return;
				}
			}
			else
			{
				//A>B A>D>C
				if (B<C)
				{
					//A>D>C>B
					Array[Offset+0]=B;Array[Offset+1]=C;Array[Offset+2]=D;Array[Offset+3]=A;return;
				}
				else
				{
					//A>B>C A>D>C
					if (B>D)
					{
						//A>B>D>C
						Array[Offset+0]=C;Array[Offset+1]=D;Array[Offset+2]=B;Array[Offset+3]=A;return;
					}
					else
					{
						//A>D>B>C
						Array[Offset+0]=C;Array[Offset+1]=B;Array[Offset+2]=D;Array[Offset+3]=A;return;
					}
				}
			}
		}
	}
	else
	{
		// B>A
		if (C>D)
		{
			// B>A C>D
			if (C>B)
			{
				// C>B>A C>D
				if (D<B)
				{
					// C>B>A C>D D<B
					if (D<A)
					{
						// C>B>A>D
						Array[Offset+0]=D;Array[Offset+1]=A;Array[Offset+2]=B;Array[Offset+3]=C;return;
					}
					else
					{
						// C>B>D>A
						Array[Offset+0]=A;Array[Offset+1]=D;Array[Offset+2]=B;Array[Offset+3]=C;return;
					}
				}
				else
				{
					// C>D>B>A
					Array[Offset+0]=A;Array[Offset+1]=B;Array[Offset+2]=D;Array[Offset+3]=C;return;
				}
			}
			else
			{
				// B>A B>C C>D
				if (A>C)
				{
					//B>A>C>D
					Array[Offset+0]=D;Array[Offset+1]=C;Array[Offset+2]=A;Array[Offset+3]=B;return;
				}
				else
				{
					//B>C>A C>D
					if (D>A)
					{
						//B>C>D>A
						Array[Offset+0]=A;Array[Offset+1]=D;Array[Offset+2]=C;Array[Offset+3]=B;return;
					}
					else
					{
						//B>C>A>D
						Array[Offset+0]=D;Array[Offset+1]=A;Array[Offset+2]=C;Array[Offset+3]=B;return;
					}
				}
			}
		}
		else
		{
			// B>A D>C
			if (D>B)
			{
				//D>B>A D>C
				if (C>A)
				{
					//D>B>A D>C>A
					if (C>B)
					{
						//D>C>B>A
						Array[Offset+0]=A;Array[Offset+1]=B;Array[Offset+2]=C;Array[Offset+3]=D;return;
					}
					else
					{
						//D>B>C>A
						Array[Offset+0]=A;Array[Offset+1]=C;Array[Offset+2]=B;Array[Offset+3]=D;return;
					}
				}
				else
				{
					//D>B>A>C
					Array[Offset+0]=C;Array[Offset+1]=A;Array[Offset+2]=B;Array[Offset+3]=D;return;
				}
			}
			else
			{
				//B>A B>D>C
				if (A<C)
				{
					//B>D>C>A
					Array[Offset+0]=A;Array[Offset+1]=C;Array[Offset+2]=D;Array[Offset+3]=B;return;
				}
				else
				{
					//B>A>C B>D>C
					if (A>D)
					{
						//B>A>D>C
						Array[Offset+0]=C;Array[Offset+1]=D;Array[Offset+2]=A;Array[Offset+3]=B;return;
					}
					else
					{
						//B>D>A>C
						Array[Offset+0]=C;Array[Offset+1]=A;Array[Offset+2]=D;Array[Offset+3]=B;return;
					}
				}
			}
		}
	}
}

inline void Sort_Rapid5(int *Array, int Offset)
{
	
	Sort_Rapid4(Array, Offset);
	Sort_Rapid4(Array, Offset+1);
	Sort_Rapid2(Array, Offset);
	
	
	/* Should be possible in 7 comparisons (one above takes 11) */
}